#include <algorithm>

namespace bga
{

template< typename T >
DepthFirstTreeIterator<T>::DepthFirstTreeIterator(const Node<T>& node) : Iterator<T>(), root(&node), begin(true)
{
}

template< typename T >
DepthFirstTreeIterator<T>::~DepthFirstTreeIterator()
{

}

template< typename T >
bool DepthFirstTreeIterator<T>::hasNext()
{
    bool res = false;

    if(currentIterator != root->childrenList.end() || begin == true)
    {
        res = true;
    }

    return res;

    /// At first, we handle the children of the node
    /*if(currentElement->getLeftChild() != NULL)
    {
        currentElement = currentElement->getLeftChild();
        res = true;
    }
    /// Else, we handle the next brother of the current node
    else if(currentElement->getRightChild() != NULL)
    {
        currentElement = currentElement->getRightChild();
        res = true;
    }
    /// if the current node has nor children neither brother, we search the nearest brother of its parents
    else
    {
        const Node<T>* parent = currentElement->getParent();
        /// Try to simplify the condition
        while((parent != NULL && parent->getRightChild() == NULL) || (parent != NULL && parent->getRightChild() != NULL && parent->getRightChild() == currentElement))
        {
            currentElement = parent;
            parent = parent->getParent();
        }
        if(parent != NULL)
        {
            currentElement = parent->getRightChild();
            res = true;
        }
    }*/
   // return res;
}

template< typename T >
T* DepthFirstTreeIterator<T>::next()
{
    if(begin == true)
    {
        begin = false;
        currentIterator = root->childrenList.begin();
        return root->getElement();
    }
    else
    {
        T* element = (*currentIterator)->getElement();
        if((*currentIterator)->childrenList.size() != 0)
        {
            stackIterator.push(currentIterator);
            currentIterator = (*currentIterator)->childrenList.begin();
        }
        else
        {
            /// Get up to the first iterator valid, if empty
            goNext();
        }

        return element;
    }

}

template< typename T >
void DepthFirstTreeIterator<T>::goNext()
{
    Node<T>* node = (*currentIterator)->getParent();
    /// No children
    ++currentIterator;

    if(currentIterator == node->childrenList.end())
    {
        currentIterator = stackIterator.top();
        stackIterator.pop();
        goNext();
    }
}

}
